The present invention relates to a method and system for autonomously developing geospatially specific knowledge and, more particularly, to developing or augmenting a geographic information system database by utilizing indiscriminately gathered actual probe data.
With the advance of information technologies, in particular computer processing, communications and global positioning, systems and processes have been developed to utilize these technologies to provide useful information. For example, satellite based positioning systems, such as the U.S. Global Positioning System (GPS) and the Russian Global Navigation Satellite System (GLONASS) provide position information used in vehicle and personal navigation, such as for aircraft, marine-based vehicles, land-based vehicles, as well as an individual""s own use. The GPS and GLONASS systems provide an absolute position anywhere on the earth where at least four satellites can be clearly observed. Using known differential techniques, a positional accuracy of one meter or less can often be obtained.
It is also known to use fleets of probe vehicles, such as cars and trucks, equipped with differential GPS (DGPS) receivers to provide raw data along particular routes in order to monitor traffic flow. Such a system is described in U.S. Pat. No. 5,539,645, wherein a central computer receives collected and reported baseline data from probe vehicles concerning time varying quantities along selected routes. This xe2x80x9crawxe2x80x9d calibration data is modeled to determine normal traffic speeds and patterns, which are compared with monitored data. Deviations outside acceptable variations are reported to the central processor, which can then determine variously occurring traffic events. This reference describes a desirable position information accuracy of, for example, 0.5 meters, in order to distinguish lane changes and particular lanes of a multi-lane roadway being travelled. While such a known DGPS receiver may have the requisite accuracy to locate a vehicle within a particular lane, it has not previously been possible to reliably determine the lane locations themselves.
German Patent documents DE 195 25 291 and DE 196 50 844 describe methods for analyzing information received from probe vehicles traveling a current route in order to associate the information as attributes of corresponding road sections in a digital street map. The attributes provide navigation information for the vehicle to travel a particular route. The German ""844 reference stores static and dynamic parameters for the detected route in the digital map. These static parameters include structural characteristics of the path driven. The dynamic parameters are continually adapted to the real conditions of the detected route street sections in order to determine a vehicle drive route. Both of these systems attempt to provide reliable traffic guidance and navigation information.
All of the above-described known systems utilize DGPS position information in conjunction with conventionally obtained digital road maps in order to assist in navigation by determining preferred routes and/or by providing traffic monitoring information. In the future, advanced safety and navigation applications in vehicles will require highly accurate and detailed digital maps useful in conjunction with the global positioning systems. The construction of such detailed digital maps has not previously been readily possible due to the expensive and time-consuming nature of manual lane measurements over countless road miles in the road networks.
Attempts have been made at automated mapping systems. For example, the reference xe2x80x9cPositioning Accuracy of the GPSvanxe2x80x9d, Proceedings of the 52nd Annual National Technical Meeting of the Institute of Navigation, pp. 657-665, Palm Springs, Calif., 1995, describes a special-purpose, labor-intensive effort to exhaustively map a target area. Here, a specially equipped vehicle in the form of a GPSvan combines numerous sensors, including multiple GPS receivers, laser cameras and stereo vision systems, to capture detailed information about the roadway traveled upon. Such vehicles are, however, prohibitively expensive and require dedicated personnel to encode features as the vehicle drives.
There is therefore needed an automatic method and system to develop, refine and augment digital maps to provide the requisite geospatial accuracy for future fields relating to safety, navigation, marketing, etc.
The present invention meets these needs by developing geospatial information concerning a particular area using a plurality of uncoordinated probe systems moving in the area. The method includes the steps of obtaining probe system specific geospatial information of a lower quality from the plurality of probe systems moving in the area. Next, the probe system specific information is combined over time into a data set. The data set is then analyzed to determine higher quality geospatial information for the particular area. This xe2x80x9cdata-miningxe2x80x9d system and method can be used to develop and/or refine digital maps based on position traces (the geospatial information) generated from the probe systems equipped with global positioning system receivers having differential corrections.
Although the method and system according to the present invention will be described in detail with reference to probe vehicles providing positional trace information to refine and augment commercially available digital road maps, it will be understood that the invention is more generally applicable to using uncoordinated probe systems, having only poor or moderate quality GPS receivers, to develop geographical databases, such as maps, that are of a medium to high quality. Moreover, the probe systems can refine and augment any known database having a geographic component using a suitable number of position traces obtained from the probe systems, be they vehicular or otherwise.
According to the invention, a large number of probe vehicles are equipped with a position/time sensor to record their position and time whenever the probe vehicle is in motion. Other sensors and data types may also be combined with this data. In fact, the time data is not even necessary. The probe vehicles are driven in their normal fashion such that, over a period of time, all possible road routes will be traversed by at least one of the probe vehicles. The data from the probe vehicles is combined into a data set, either in real-time or via post-processing. This data set is then subject to statistical and/or other forms of analysis to identify various features. Based upon the data from many probe vehicles, its combination provides highly accurate measurements of the physical environment. A map is then generated from the accurate measurements. This thus provides a probabilistic approach to generating a map which is advantageous for autonomous vehicle applications in that it describes how people actually behave on a road network. Further advantageously, statistical evaluation of the data set provides information apart from the road geometry, such as traffic control information. When the position data is combined with data from other vehicle sensors, such as traction control, suspension, turn indicators, vision systems, automotive radar, etc., it becomes possible to locate other environmental conditions such as potholes, dirt roads, ice on the roads, guard rails, etc.
In a particular embodiment, the present invention advantageously builds and/or enhances digital road maps, which serve as a baseline map, with geospatially specific information by mining massive amounts of differential global positioning system (DGPS) trace data from uncoordinated probe vehicles.
When building the digital road map, the initial trace data from the uncoordinated probe vehicles serves as a base line map, which is refined based on the additional trace data. When augmenting or enhancing a commercially available digital road map, the data from the commercially available digital road map serves as the base line map, with the additional trace data from the uncoordinated probe vehicles refining the base line map data.
In an advantageous embodiment described herein, the DGPS traces from the uncoordinated probe vehicles are mined to enhance digital road maps with descriptions of lane structure including the number of lanes and their locations. The use of uncoordinated probe vehicles allows for unobtrusive and indiscriminate gathering of data from the multitude of drivers going about their ordinary business. The system does not require any special vehicles or expensive hardware to collect the data, relying on probe vehicles equipped with known DGPS systems. The resultant traces from the probe vehicles are mined for knowledge about the road network, in particular, vehicle lane information.
The system and method according to the invention determines a xe2x80x9cvirtualxe2x80x9d centerline of a road, and then determines the actual road lanes using the virtual centerline. While the invention is described with respect to a xe2x80x9cvirtualxe2x80x9d road centerline, it should be understood that this virtual centerline is an arbitrary convenience and that any line parallel to the road can be considered the virtual centerline. Beginning with the commercially available digital map serving as a baseline, the centerline from the digital map is brought into alignment with the DGPS traces from the probe vehicles traveling over a particular road segment. In general, this is done by computing the xe2x80x9caveragexe2x80x9d between the current centerline and a new trace, weighted by a confidence factor in the centerline and the trace. As the system incrementally incorporates more traces into the average, errors in the traces are averaged out such that the new centerline is more accurate than any of the traces used to develop it.
While the original centerline in the digital map is not accurate enough to be used to compute constant lane xe2x80x9coffsetsxe2x80x9d in order to identify vehicle lanes, the present invention recognizes that, by definition, any line parallel to the true vehicle lanes must be a constant perpendicular distance (hence xe2x80x9coffsetxe2x80x9d) from the vehicle lanes. Thus, the determination of a xe2x80x9cvirtualxe2x80x9d centerlinexe2x80x94based on the original centerline in the digital map and the multiple traces from the probe vehiclesxe2x80x94better serves to determine the offset amounts in order to identify the actual vehicle lanes. These offsets are defined by the perpendicular distance of the vehicle lane to the virtual centerline, since all of the vehicle lanes are parallel to one another.
By assuming vehicle drivers are generally within a vehicle lane, the perpendicular distance from most positions of the vehicle to the virtual centerline provides an estimate of the offset for the particular lane being travelled. The method and system thus calculate an offset amount for each position in the position trace. These offsets are then grouped into lanes and averaged to find the vehicle lane centerline. A hierarchical agglomerative clustering-type algorithm is advantageously used to model the actual vehicle lanes and refine the digital road map based on the accurately represented virtual centerline of the road segment. According to the present invention, lane modeling is accomplished for a target road segment S, covered by a set of position traces P from probe vehicles, by first finding the accurate virtual centerline for the target road segment S using the set of position traces P, and then clustering P""s offsets from the virtual centerline into the lane information.
The present invention can therefore build or augment digital maps with lane information, creating a resource usable by any lane-related automotive application. The computed lane models enable both safety applications, such as lane keeping, and convenience applications, such as lane-changing advice. The large number of positional traces obtained from the probe vehicles provides an inexpensive and automated method to compute the lane models, as well as other geographic information, such as traffic signals, stop signs, elevational changes, etc. For example, a combined digital road map built or enhanced with accurate lane modeled information in conjunction with an in-car positioning system advantageously enables: a lane departure warning/lane keeping safety application, a lane-level navigation application, and dynamic lane closure applications.
The lane departure warning/lane keeping safety application tracks a vehicle""s current offset from the road/lane centerline. If the offset deviates more than a defined threshold amount, a warning signal is activated. Alternatively, the vehicle itself could assume control to avoid potential accidents. The defined threshold amount can advantageously be related to a standard deviation of the offsets during typical driving conditions. High positional accuracy is required with this safety application.
The lane-level navigation application enhances conventionally known standard road level navigation. The lane-level navigation advises the driver as to the specific lane one should choose to reach a particular destination without excessive and last-minute lane changing. In addition to the lane modeling information, lane-level navigation requires a model concerning the vehicle behavior at route intersections on a per-lane basis. For example, the position traces from the probe vehicles may indicate that 100% of drivers in the left lane at a particular intersection turn left, while 50% of drivers in the right lane go straight and 50% turn right.
The dynamic lane closure application makes comparisons between current road segment lane occupancy and past road segment lane occupancy if the aggregate data on lane occupancy is available dynamically via wireless communications. If a particular lane is under-occupied, the dynamic lane closure application infers that the lane is closed, for example, due to an accident or construction. Vehicle navigation systems can then factor this into account when calculating vehicle routes.
Of course, the lane modeling information according to the present invention can be used with other safety and convenience applications not described herein to provide additional driver benefits. Examples of applications enabled by the combination of a digital road map with accurate lane models and in-car positioning systems are described in the paper entitled xe2x80x9cThe Potential of Precision Maps in Intelligent Vehiclesxe2x80x9d, Proceedings of the IEEE International Conference on Intelligent Vehicles, pages 419-422, Stuttgart, Germany, Oct. 1998, the contents of which are expressly incorporated by reference herein.
Prior known approaches to determine lane boundaries attempt to do so directly, such as by using vehicle-mounted machine vision systems to find lane markings in relation to the vehicle position. The present invention, however, effectively allows the driver""s lane keeping ability to identify the center of the lane. The prior approaches encountered numerous limitations. First, the machine vision system had to be correctly calibrated to the lane markings sensed. For a vision based system, machine recognizable lane features of some type are required. Second, it is difficult if not impossible to build an accurate database of lane models from machine vision systems alone, or any other relative sensing method for that matter. This is because the straight-forward approach to building such a database stores the lane structures in a spatially absolute reference system. Vehicles without an absolute sensing method, such as GPS equipped vehicles, have no way to register the data spatially, and consequently, no way to look ahead around corners and over hills for example.
As noted above, the present invention relies on DGPS traces from probe vehicles to effectively let the driver""s lane keeping ability identify the center of the lane. The absolute nature of this data provides information on upcoming terrain which is not directly sensible from the vehicle. This builds an accurate database of lane models.
In an advantageous embodiment with respect to lane keeping applications of the present invention, machine vision techniques are additionally incorporated in the event the GPS accuracy suffers, such as when one or more satellite views are partially or totally obstructed. The use of local sensors, such as the machine vision systems, can compensate for the satellite visibility problems. This enhances the positional accuracy available for the vehicle in order to perform the lane keeping functions.
Other objects, advantages and novel features of the present invention will become apparent from the following detailed description of the invention when considered in conjunction with the accompanying drawings.